import java.util.ArrayList;
import java.util.HashMap;

public class FirstSet {
    // 存储文法规则
    ArrayList<Formula> formulas;
    // 存储终结符
    ArrayList<String> terminals;
    // 存储非终结符
    ArrayList<String> nonTerminals;
    // 存储每个符号的 First 集合
    HashMap<String, ArrayList<String>> firsts;

    /**
     * 计算 First 集合
     * 
     * @param _formulas     产生式列表
     * @param _terminals    终结符列表
     * @param _nonTerminals 非终结符列表
     * @param _firsts       存储每个符号的 First 集合
     */
    public void setFirst(ArrayList<Formula> formulas, ArrayList<String> terminals,
            ArrayList<String> nonTerminals, HashMap<String, ArrayList<String>> firsts) {
        this.formulas = formulas;
        this.terminals = terminals;
        this.nonTerminals = nonTerminals;
        this.firsts = firsts;

        // 初始化终结符的 First 集合
        for (String terminal : terminals) {
            ArrayList<String> first = new ArrayList<>();
            first.add(terminal); // 终结符的 First 集合就是它本身
            firsts.put(terminal, first);
        }

        // 初始化非终结符的 First 集合
        for (String nonTerminal : nonTerminals) {
            ArrayList<String> first = new ArrayList<>();
            firsts.put(nonTerminal, first);
        }

        boolean flag;
        // 迭代计算 First 集合，直到没有更新
        while (true) {
            flag = true; // 标记是否有更新
            // 遍历所有文法规则
            for (Formula formula : formulas) {
                String left = formula.getLeft(); // 左边的非终结符
                String[] rights = formula.getRight(); // 右边的符号串

                // 遍历产生式右侧的符号串
                for (String right : rights) {
                    // 如果右侧符号是终结符，则直接加入到左侧非终结符的 First 集合中
                    if (terminals.contains(right)) {
                        if (!firsts.get(left).contains(right)) {
                            firsts.get(left).add(right);
                            flag = false;
                        }
                        break; // 终结符一旦加入，直接跳出
                    }

                    // 如果右侧符号是非终结符
                    if (nonTerminals.contains(right)) {
                        // 将该非终结符的 First 集合中的元素加入到左侧非终结符的 First 集合中
                        ArrayList<String> rightFirst = firsts.get(right);
                        for (String firstSymbol : rightFirst) {
                            // 如果右侧的 First 集合中没有包含这个符号，则加入
                            if (!firsts.get(left).contains(firstSymbol)) {
                                firsts.get(left).add(firstSymbol);
                                flag = false;
                            }
                        }

                        // 如果右侧符号的 First 集合包含空串 ε，则继续检查后面的符号
                        if (!rightFirst.contains("$")) {
                            break;
                        }
                    }
                }
            }
            // 如果没有任何更新，说明计算完成
            if (flag) {
                break;
            }
        }
    }

    // 判断是否产生$，也就是没了
    public boolean isCanBeNull(ArrayList<Formula> formulas, String symbol) {
        String[] rights;
        // 遍历每个文法
        for (Formula formula : formulas) {
            // 寻找产生式
            if (formula.getLeft().equals(symbol)) {
                // symbol->[rights]
                rights = formula.getRight();
                if (rights[0].equals("$")) {
                    // e.g:symbol->$
                    return true;
                }
            }
        }
        return false;
    }
}